from typing import List


class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        wordDict = set(wordDict)
        n = len(s)
        self.ans = []
        def dfs(start_index:int, words:list[str]):
            if start_index >= n:
                self.ans.append(" ".join(words))
                return
            # 启动位，组好的单词
            for j in range(start_index, n):
                if s[start_index:j+1] in wordDict:
                    words.append(s[start_index:j+1])
                    dfs(j+1, words)
                    words.pop()
        dfs(0,[])
        return self.ans

if __name__ == '__main__':
    s = Solution()
    r = s.wordBreak(s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"])
    print(r)